#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
//#include <math.h>
//int cnt(int num, int len)
//{
//	if(num/10 != 0)
//		return cnt(num / 10, len) + pow(num % 10, len);
//	if (num / 10 == 0)
//		return pow(num, len);
//}
//int main()
//{
//	int num = 0;
//	int num1 = 0;
//	for (num = 0; num < 100001; num++)
//	{
//		num1 = num;
//		int len = 1;
//		while (num1 /= 10)
//		{
//			len++;
//		}
//		if (num == cnt(num, len))
//			printf("%d ", num);
//	}
//	return 0;
//}

//#include <stdio.h>
//#include <string.h>
//int main()
//{
//    int line = 0;
//    while (scanf("%d", &line) != 0)
//    {
//        char arr[line+1];
//        for (int i = 0; i < line; i++)
//        {
//            arr[i] = ' ';
//        }
//        arr[line] = '\0';
//        int line1 = line;
//        char str[line+1];
//        int i = 0;
//        for (int j = 0; j < line; j++)
//        {
//            int left = i;
//            int right = line - 1 - i;
//            strcpy(str, arr);
//            str[left] = '*';
//            str[right] = '*';
//
//            for (int k = 0; k < line; k++)
//            {
//                printf("%c", str[k]);
//            }
//            i++;
//            printf("\n");
//        }
//    }
//    return 0;
//}

//int main()
//{
//	int inputNum = 5;
//
//	for (int i = 0; i < inputNum; i++)
//	{
//		int starIndex_1 = i;
//		int starIndex_2 = inputNum - 1 - i;
//		for (int j = 0; j < inputNum; j++)
//		{
//			if (j == starIndex_1 || j == starIndex_2)
//			{
//				printf("*");
//			}
//			else
//			{
//				printf(" ");
//			}
//			printf("\n");
//		}
//	}
//}


//#include <stdio.h>
//int arr4[30000] = { 0 };
//int main()
//{
//    int n, m;
//    scanf("%d %d", &n, &m);
//    int arr1[n], arr2[m], arr3[n + m];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &arr1[i]);
//    }
//    for (int i = 0; i < m; i++)
//    {
//        scanf("%d", &arr2[i]);
//    }
//    for (int i = 0; i < m + n; i++)
//    {
//        if (i < n)
//            arr3[i] = arr1[i];
//        if (i >= n)
//            arr3[i] = arr2[i - n];
//    }
//    for (int i = 0; i < m + n; i++)
//    {
//        arr4[arr3[i]]++;
//    }
//    for (int i = 0; i <= 30000; i++)
//    {
//        while (arr4[i] != 0)
//        {
//            printf("%d ", i);
//            arr4[i]--;
//        }
//    }
//    return 0;
//}

//#include <stdio.h>
//
//int main()
//{
//    int input = 0;
//    while (scanf("%d", &input) != EOF)
//    {
//        int i = 0, j = 0;
//        while (input)
//        {
//            for (i = 0; i < input * 2; i++)
//            {
//                printf(" ");
//            }
//            input--;
//            j++;
//            for (int k = 0; k < j; k++)
//            {
//                printf("*");
//            }
//            printf("\n");
//        }
//        for (i = 0; i < j + 1; i++)
//        {
//            printf("*");
//        }
//        printf("\n");
//        while (j)
//        {
//            input++;
//            for (i = 0; i < input * 2; i++)
//            {
//                printf(" ");
//            }
//            for (int k = 0; k < j; k++)
//            {
//                printf("*");
//            }
//            printf("\n");
//            j--;
//        }
//    }
//
//
//    return 0;
//}